package pers.sloera.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * <p>
 * <p>
 * <p>
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：n = 1
 * 输出：[["Q"]]
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 1 <= n <= 9
 * <p>
 * <p>
 * <p>
 * Related Topics 数组 回溯 👍 1267 👎 0
 */

//leetcode submit region begin(Prohibit modification and deletion)
class Solution51 {
    // class Solution {

    /**
     * @param loc 每行中n皇后的位置。由于皇后不能同行，所以每行肯定只有一个皇后，用一个一维数组存放位置即可
     * @param row 当前行数
     */
    private boolean hereValid(int[] loc, int row) {
        //　和所有之前行的数进行比较
        for (int i = 0; i < row; i++) {
            // 判断是否在同一列及同一行 斜线包括左上到右下和右下到左上，所以加绝对值
            // 由于之前已经判断了不能为同一行，所以只需要判断是否为同一列和斜线即可
            if (loc[row] == loc[i] || Math.abs(loc[row] - loc[i]) == row - i) {
                return false;
            }
        }
        return true;
    }

    /**
     * 回溯处理各行
     *
     * @param totalRow 总共有多少行
     * @param loc 每行中n皇后的位置。由于皇后不能同行，所以每行肯定只有一个皇后，用一个一维数组存放位置即可
     * @param curRow 当前处理的行数
     * @param res 结果存放
     */
    private void queen(int totalRow, int[] loc, int curRow, List<List<String>> res) {
        // // 如果只需要找到一个解
        // if (res.size() > 0) {
        //   return;
        // }
        // 遍历完所有的行，输出结果
        if (curRow == totalRow) {
            // 添加当前loc
            List<String> list = new ArrayList<>();
            // 遍历行
            for (int i = 0; i < totalRow; i++) {
                char[] temp = new char[totalRow];
                // 遍历列
                for (int j = 0; j < totalRow; j++) {
                    // 找到皇后所在的列
                    if (j + 1 == loc[i]) {
                        temp[j] = 'Q';
                    } else temp[j] = '.';
                }
                list.add(String.valueOf(temp));
            }
            res.add(list);
            //			return;

        } else {
            // 处理每列
            for (int i = 0; i < totalRow; i++) {
                // 前置处理，假定当前行放在当前列
                // i+1 是因为，为0代表不放
                loc[curRow] = i + 1;
                if (hereValid(loc, curRow)) {
                    queen(totalRow, loc, curRow + 1, res);
                }
                // 后置处理，将当前行位置清0
                loc[curRow] = 0;
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        // 存储每行皇后的位置
        int[] loc = new int[n];
        queen(n, loc, 0, res);
        return res;
    }
}

//leetcode submit region end(Prohibit modification and deletion)
